{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Reverse Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #ordered-set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #有序集合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minReverseOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最少翻转操作数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;和一个在范围 <code>[0, n - 1]</code>&nbsp;以内的整数&nbsp;<code>p</code>&nbsp;，它们表示一个长度为 <code>n</code> 且下标从 <strong>0</strong>&nbsp;开始的数组&nbsp;<code>arr</code>&nbsp;，数组中除了下标为&nbsp;<code>p</code>&nbsp;处是 <code>1</code>&nbsp;以外，其他所有数都是 <code>0</code>&nbsp;。</p>\n",
    "\n",
    "<p>同时给你一个整数数组&nbsp;<code>banned</code>&nbsp;，它包含数组中的一些位置。<code>banned</code>&nbsp;中第&nbsp;<strong>i</strong>&nbsp;个位置表示&nbsp;<code>arr[banned[i]] = 0</code>&nbsp;，题目保证&nbsp;<code>banned[i] != p</code>&nbsp;。</p>\n",
    "\n",
    "<p>你可以对 <code>arr</code>&nbsp;进行 <strong>若干次</strong>&nbsp;操作。一次操作中，你选择大小为 <code>k</code>&nbsp;的一个 <strong>子数组</strong>&nbsp;，并将它 <b>翻转</b>&nbsp;。在任何一次翻转操作后，你都需要确保 <code>arr</code>&nbsp;中唯一的 <code>1</code>&nbsp;不会到达任何 <code>banned</code>&nbsp;中的位置。换句话说，<code>arr[banned[i]]</code>&nbsp;始终&nbsp;<strong>保持</strong>&nbsp;<code>0</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回一个数组&nbsp;<code>ans</code>&nbsp;，对于<em>&nbsp;</em><code>[0, n - 1]</code>&nbsp;之间的任意下标&nbsp;<code>i</code>&nbsp;，<code>ans[i]</code>&nbsp;是将&nbsp;<code>1</code>&nbsp;放到位置&nbsp;<code>i</code>&nbsp;处的&nbsp;<strong>最少</strong>&nbsp;翻转操作次数，如果无法放到位置&nbsp;<code>i</code>&nbsp;处，此数为&nbsp;<code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>子数组</strong>&nbsp;指的是一个数组里一段连续 <strong>非空</strong>&nbsp;的元素序列。</li>\n",
    "\t<li>对于所有的 <code>i</code>&nbsp;，<code>ans[i]</code>&nbsp;相互之间独立计算。</li>\n",
    "\t<li>将一个数组中的元素 <strong>翻转</strong> 指的是将数组中的值变成 <strong>相反顺序</strong>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, p = 0, banned = [1,2], k = 4\n",
    "<b>输出：</b>[0,-1,-1,1]\n",
    "<b>解释：</b><code>k = 4，所以只有一种可行的翻转操作，就是将整个数组翻转。一开始 </code>1<strong> </strong>在位置 0 处，所以将它翻转到位置 0 处需要的操作数为 0 。\n",
    "我们不能将 1 翻转到 banned 中的位置，所以位置 1 和 2 处的答案都是 -1 。\n",
    "通过一次翻转操作，可以将 1 放到位置 3 处，所以位置 3 的答案是 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 5, p = 0, banned = [2,4], k = 3\n",
    "<b>输出：</b>[0,-1,-1,-1,-1]\n",
    "<b>解释：</b>这个例子中 1 一开始在位置 0 处，所以此下标的答案为 0 。\n",
    "翻转的子数组长度为 k = 3 ，1 此时在位置 0 处，所以我们可以翻转子数组 [0, 2]，但翻转后的下标 2 在 banned 中，所以不能执行此操作。\n",
    "由于 1 没法离开位置 0 ，所以其他位置的答案都是 -1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, p = 2, banned = [0,1,3], k = 1\n",
    "<b>输出：</b>[-1,-1,0,-1]\n",
    "<b>解释：</b>这个例子中，我们只能对长度为 1 的子数组执行翻转操作，所以 1 无法离开初始位置。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= p &lt;= n - 1</code></li>\n",
    "\t<li><code>0 &lt;= banned.length &lt;= n - 1</code></li>\n",
    "\t<li><code>0 &lt;= banned[i] &lt;= n - 1</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n&nbsp;</code></li>\n",
    "\t<li><code>banned[i] != p</code></li>\n",
    "\t<li><code>banned</code>&nbsp;中的值 <strong>互不相同</strong>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-reverse-operations](https://leetcode.cn/problems/minimum-reverse-operations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-reverse-operations](https://leetcode.cn/problems/minimum-reverse-operations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n0\\n[1,2]\\n4', '5\\n0\\n[2,4]\\n3', '4\\n2\\n[0,1,3]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from typing import List, Optional, Tuple\n",
    "\n",
    "INF = int(1e18)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        def getRange(i: int) -> Tuple[int, int]:\n",
    "            \"\"\"反转长度为k的子数组,从i可以到达的左右边界闭区间.\"\"\"\n",
    "            return max(i - k + 1, k - i - 1), min(i + k - 1, 2 * n - k - i - 1)\n",
    "\n",
    "        def setUsed(u: int) -> None:\n",
    "            \"\"\"将u位置标记为已经访问过.\"\"\"\n",
    "            finder[u & 1].erase(u)\n",
    "\n",
    "        def findUnused(u: int) -> Optional[int]:\n",
    "            \"\"\"找到一个未使用的位置.如果不存在,返回None.\"\"\"\n",
    "            left, right = getRange(u)\n",
    "            pre = finder[(u + k + 1) & 1].prev(right)\n",
    "            if pre is not None and left <= pre <= right:\n",
    "                return pre\n",
    "            next_ = finder[(u + k + 1) & 1].next(left)\n",
    "            if next_ is not None and left <= next_ <= right:\n",
    "                return next_\n",
    "\n",
    "        finder = [Finder(n) for _ in range(2)]\n",
    "        for i in range(n):\n",
    "            finder[i & 1].insert(i)\n",
    "        for i in banned:\n",
    "            finder[i & 1].erase(i)\n",
    "        finder[p & 1].erase(p)\n",
    "\n",
    "        ########################################################\n",
    "        dist = [INF] * n\n",
    "        dist[p] = 0\n",
    "        queue = deque([p])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            while True:\n",
    "                next_ = findUnused(cur)\n",
    "                if next_ is None:\n",
    "                    break\n",
    "                dist[next_] = dist[cur] + 1\n",
    "                queue.append(next_)\n",
    "                setUsed(next_)\n",
    "        return [d if d != INF else -1 for d in dist]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Finder:\n",
    "    \"\"\"利用位运算寻找区间的某个位置左侧/右侧第一个未被访问过的位置.\n",
    "    初始时,所有位置都未被访问过.\n",
    "    \"\"\"\n",
    "\n",
    "    __slots__ = \"_n\", \"_lg\", \"_seg\"\n",
    "\n",
    "    @staticmethod\n",
    "    def _trailingZeros1024(x: int) -> int:\n",
    "        if x == 0:\n",
    "            return 1 << 10\n",
    "        return (x & -x).bit_length() - 1\n",
    "\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self._n = n\n",
    "        seg = []\n",
    "        while True:\n",
    "            seg.append([0] * ((n + (1 << 10) - 1) >> 10))\n",
    "            n = (n + (1 << 10) - 1) >> 10\n",
    "            if n <= 1:\n",
    "                break\n",
    "        self._seg = seg\n",
    "        self._lg = len(seg)\n",
    "\n",
    "    def insert(self, i: int) -> None:\n",
    "        for h in range(self._lg):\n",
    "            self._seg[h][i >> 10] |= 1 << (i % (1 << 10))\n",
    "            i >>= 10\n",
    "\n",
    "    def erase(self, i: int) -> None:\n",
    "        for h in range(self._lg):\n",
    "            self._seg[h][i >> 10] &= ~(1 << (i % (1 << 10)))\n",
    "            if self._seg[h][i >> 10]:\n",
    "                break\n",
    "            i >>= 10\n",
    "\n",
    "    def next(self, i: int) -> Optional[int]:\n",
    "        \"\"\"返回x右侧第一个未被访问过的位置(包含x).\n",
    "        如果不存在,返回None.\n",
    "        \"\"\"\n",
    "        if i < 0:\n",
    "            i = 0\n",
    "        if i >= self._n:\n",
    "            return\n",
    "        seg = self._seg\n",
    "        for h in range(self._lg):\n",
    "            if i >> 10 == len(seg[h]):\n",
    "                break\n",
    "            d = seg[h][i >> 10] >> (i % (1 << 10))\n",
    "            if d == 0:\n",
    "                i = i >> 10 + 1\n",
    "                continue\n",
    "            i += self._trailingZeros1024(d)\n",
    "            for g in range(h - 1, -1, -1):\n",
    "                i *= 1 << 10\n",
    "                i += self._trailingZeros1024(seg[g][i >> 10])\n",
    "            return i\n",
    "\n",
    "    def prev(self, i: int) -> Optional[int]:\n",
    "        \"\"\"返回x左侧第一个未被访问过的位置(包含x).\n",
    "        如果不存在,返回None.\n",
    "        \"\"\"\n",
    "        if i < 0:\n",
    "            return\n",
    "        if i >= self._n:\n",
    "            i = self._n - 1\n",
    "        seg = self._seg\n",
    "        for h in range(self._lg):\n",
    "            if i == -1:\n",
    "                break\n",
    "            d = seg[h][i >> 10] << ((1 << 10) - 1 - i % (1 << 10)) & ((1 << (1 << 10)) - 1)\n",
    "            if d == 0:\n",
    "                i = (i >> 10) - 1\n",
    "                continue\n",
    "            i += d.bit_length() - (1 << 10)\n",
    "            for g in range(h - 1, -1, -1):\n",
    "                i *= 1 << 10\n",
    "                i += (seg[g][i >> 10]).bit_length() - 1\n",
    "            return i\n",
    "\n",
    "    def islice(self, begin: int, end: int):\n",
    "        \"\"\"遍历[start,end)区间内的元素.\"\"\"\n",
    "        x = begin - 1\n",
    "        while True:\n",
    "            x = self.next(x + 1)\n",
    "            if x is None or x >= end:\n",
    "                break\n",
    "            yield x\n",
    "\n",
    "    def __contains__(self, i: int) -> bool:\n",
    "        return self._seg[0][i >> 10] & (1 << (i % (1 << 10))) != 0\n",
    "\n",
    "    def __iter__(self):\n",
    "        yield from self.islice(0, self._n)\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"FastSet({list(self)})\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        # bs = set(banned)\n",
    "        dp = [0] * n\n",
    "        q = deque()\n",
    "        q.append(p)\n",
    "        dp[p] = 0\n",
    "        for b in banned:\n",
    "            dp[b] = -1\n",
    "        odd = SortedList()\n",
    "        even = SortedList()\n",
    "        for i in range(n):\n",
    "            if i & 1 and dp[i] != -1:\n",
    "                odd.add(i)\n",
    "            elif i & 1 == 0 and dp[i] != -1:\n",
    "                even.add(i)\n",
    "        if p & 1:\n",
    "            odd.remove(p)\n",
    "        else:\n",
    "            even.remove(p)\n",
    "        odd.add(n)\n",
    "        even.add(n)\n",
    "        while q:\n",
    "            tmp = q.popleft()\n",
    "            # print(tmp)\n",
    "            l = max(tmp - k + 1, k - 1 - tmp)\n",
    "            r = min(tmp + k - 1, 2 * n - 1 - k - tmp)\n",
    "            # print(tmp, l, r)\n",
    "            # print(odd, even)\n",
    "            if l & 1:\n",
    "                bl = odd.bisect_left(l)\n",
    "                # br = odd.bisect_right(r)\n",
    "                # print(bl, l, br, r)\n",
    "                # rm_ls = list()\n",
    "                while odd[bl] <= r:\n",
    "                    dp[odd[bl]] = dp[tmp] + 1\n",
    "                    q.append(odd[bl])\n",
    "                    odd.remove(odd[bl])\n",
    "                # for i in range(bl, br): \n",
    "                #     if i < len(odd) and dp[odd[i]] != -1:\n",
    "                #         dp[odd[i]] = dp[tmp] + 1\n",
    "                #         q.append(odd[i])\n",
    "                #         rm_ls.append(odd[i])\n",
    "                # for i in rm_ls:\n",
    "                #     odd.remove(i)\n",
    "            else:\n",
    "                bl = even.bisect_left(l)\n",
    "                while even[bl] <= r:\n",
    "                    dp[even[bl]] = dp[tmp] + 1\n",
    "                    q.append(even[bl])\n",
    "                    even.remove(even[bl])\n",
    "                # br = even.bisect_right(r)\n",
    "                # print(bl, l, br, r)\n",
    "                # rm_ls = list()\n",
    "                # for i in range(bl, br):\n",
    "                #     if i < len(even) and dp[even[i]] != -1:\n",
    "                #         dp[even[i]] = dp[tmp] + 1\n",
    "                #         q.append(even[i])\n",
    "                #         rm_ls.append(even[i])\n",
    "                        # even.remove(even[i])\n",
    "                # rl = [even[i] for i in range(bl, br) if i < len(even) and even[i] not in bs]\n",
    "                # for i in rm_ls:\n",
    "                #     even.remove(i)\n",
    "            # print(dp)\n",
    "        # print(odd, even)\n",
    "        for i in odd[:-1]:\n",
    "            dp[i] = -1\n",
    "        for i in even[:-1]:\n",
    "            dp[i] = -1\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        ans=[-1 for i in range(0,n)] # 答案数组，初值-1，BFS结束后无效位置就不用填了\n",
    "        ans[p]=0   \n",
    "        if k==1:\n",
    "            return ans  \n",
    "        lst = [SortedList(range(0,n,2)),SortedList(range(1,n,2))] # 奇数和偶数分别存放\n",
    "        for ke in banned:            \n",
    "            lst[ke%2].remove(ke)  # banned里的位置都是无效位置，提前删掉\n",
    "        lst[p%2].remove(p) # 初始位置答案是0，视为已处理过的位置\n",
    "        lst[0].add(n)\n",
    "        lst[1].add(n)\n",
    "        step = 1\n",
    "        q = {p}\n",
    "        while q:\n",
    "            tem = set()\n",
    "            for i in q:\n",
    "                mn=max(k-i-1,i-k+1)\n",
    "                mx=min(2*n-i-k-1,i+k-1)\n",
    "                s=lst[mn%2]\n",
    "                l=s.bisect_left(mn) #返回地址 \n",
    "                while s[l]<=mx: \n",
    "                    t=s[l]  \n",
    "                    tem.add(t)  \n",
    "                    s.remove(t)  \n",
    "                    ans[t]=step\n",
    "            q=tem\n",
    "            step+=1   \n",
    "        return ans\n",
    "                \n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        ans=[-1 for i in range(0,n)] # 答案数组，初值-1，BFS结束后无效位置就不用填了\n",
    "        ans[p]=0   \n",
    "        if k==1:\n",
    "            return ans  \n",
    "        # ans = [-1]*n # 答案数组，初值-1，BFS结束后无效位置就不用填了\n",
    "        # ans[p]=0    \n",
    "        lst = [SortedList(range(0,n,2)),SortedList(range(1,n,2))] # 奇数和偶数分别存放，井水不犯河水\n",
    "        for ke in banned:            \n",
    "            lst[ke%2].remove(ke)  # banned里的位置都是无效位置，提前删掉\n",
    "        lst[p%2].remove(p) # 初始位置答案是0，视为已处理过的位置\n",
    "        # lst=[SortedList(),SortedList()]\n",
    "        # banned=set(banned)\n",
    "        # for i in range(0,n):\n",
    "        #     if ((i!=p) & (i not in banned)):\n",
    "        #         lst[i%2].add(i)\n",
    "        lst[0].add(n)\n",
    "        lst[1].add(n)\n",
    "        step = 1\n",
    "        q = {p}\n",
    "        while q:\n",
    "            tem = set()\n",
    "            for i in q:\n",
    "                mn=max(k-i-1,i-k+1)\n",
    "                mx=min(2*n-i-k-1,i+k-1)\n",
    "                s=lst[mn%2]\n",
    "                l=s.bisect_left(mn) #返回地址 \n",
    "                #r=s.bisect_right(mx)\n",
    "                while s[l]<=mx: \n",
    "                    t=s[l]  \n",
    "                    tem.add(t)  \n",
    "                    s.remove(t)  \n",
    "                    ans[t]=step\n",
    "                # mod2 = (i+k-1)%2 #先确定翻转后的奇偶性，这决定在哪个有序数据结构里二分查找\n",
    "                # l = lst[mod2].bisect_left(max(-i+k-1,i-k+1))  # 出界和不出界分别对待，下同\n",
    "                # r = lst[mod2].bisect_right(min(2*n-i-k-1,i+k-1))                \n",
    "                # for j in range(l,r):\n",
    "                #     pos1 = lst[mod2][j]\n",
    "                #     #if pos1 in lst[mod2]:\n",
    "                #     tem.add(pos1)\n",
    "                #     lst[mod2].remove(pos1)\n",
    "                #     ans[pos1]=step\n",
    "\n",
    "            q=tem\n",
    "            step+=1   \n",
    "        return ans\n",
    "                \n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        # def have_pool(n, ans):\n",
    "        #     max=0\n",
    "        #     index=-1\n",
    "        #     for i in range(0,n):\n",
    "        #         if(ans[i]>max):\n",
    "        #             max=ans[i]\n",
    "        #             index=i\n",
    "        #     return index\n",
    "\n",
    "        # def find_left(p,k,ans,banned):\n",
    "        #     if (len(banned)>0):\n",
    "        #         flag=-1\n",
    "        #         while True:\n",
    "        #             if (p-k+1)<0:\n",
    "        #                 break \n",
    "        #             for j in range(0,len(banned)):\n",
    "        #                 if ((p-k+1) == banned[j] ):\n",
    "        #                     flag=1\n",
    "        #             if flag!=1:\n",
    "        #                 ans[p-k+1]= ans[p]+1\n",
    "        #                 p=p-k+1 \n",
    "        #             else:\n",
    "        #                 break                   \n",
    "        #     else:\n",
    "        #         while True:\n",
    "        #             if (p-k+1)<0:\n",
    "        #                 break\n",
    "        #             ans[p-k+1]= ans[p]+1  \n",
    "        #             p=p-k+1\n",
    "        #     return ans\n",
    "\n",
    "        # def find_right(n,p,k,ans,banned):\n",
    "        #     if (len(banned)>0):\n",
    "        #         flag=-1\n",
    "        #         while True:\n",
    "        #             if (p+k-1)>=n:\n",
    "        #                 break \n",
    "        #             for j in range(0,len(banned)):\n",
    "        #                 if ((p+k-1) == banned[j]) :\n",
    "        #                     flag=1\n",
    "        #             if flag!=1:\n",
    "        #                 ans[p+k-1]= ans[p]+1\n",
    "        #                 p=p+k-1 \n",
    "        #             else:\n",
    "        #                 break                   \n",
    "        #     else:\n",
    "        #         while True:\n",
    "        #             if (p+k-1)>=n:\n",
    "        #                 break\n",
    "        #             ans[p+k-1]= ans[p]+1  \n",
    "        #             p=p+k-1\n",
    "        #     return ans \n",
    "\n",
    "        # ans=[-1 for i in range(0,n)]\n",
    "        # ans[p]=0\n",
    "        # if k == 1 :\n",
    "        #     return ans\n",
    "        # if k==n:\n",
    "        #     if (len(banned) > 0):\n",
    "        #         max=0\n",
    "        #         for i in range(0,len(banned)):\n",
    "        #             if(banned[i]>max):\n",
    "        #                 max=banned[i]\n",
    "        #         if (max == n-1)|(max==0):\n",
    "        #             return ans\n",
    "        #         for i in range(0, n):\n",
    "        #             flag = -1\n",
    "        #             for j in range(0, len(banned)):\n",
    "        #                 if i == banned[j]:\n",
    "        #                     flag = 1\n",
    "        #             if ((flag != 1) & (i != p)):\n",
    "        #                 ans[i] = 1\n",
    "        #     else:\n",
    "        #         if(p-k+1)>=0:\n",
    "        #             ans[p-k+1]=1\n",
    "        #         if(p+k-1)<n:\n",
    "        #             ans[p+k-1]=1\n",
    "        #     return ans\n",
    "        \n",
    "        # find_left(p,k,ans,banned)\n",
    "        # find_right(n,p,k,ans,banned)                       \n",
    "        # return ans\n",
    "        res = [-1]*n # 答案数组，初值-1，BFS结束后无效位置就不用填了\n",
    "        res[p]=0        \n",
    "        lst = [SortedList(range(0,n,2)),SortedList(range(1,n,2))] # 奇数和偶数分别存放，井水不犯河水\n",
    "\n",
    "        for ke in banned:            \n",
    "            lst[ke%2].remove(ke)  # banned里的位置都是无效位置，提前删掉\n",
    "        lst[p%2].remove(p) # 初始位置答案是0，视为已处理过的位置\n",
    "        step = 1\n",
    "        que = {p}\n",
    "        rmv = set()\n",
    "\n",
    "        while que:\n",
    "            que1 = set()\n",
    "            for pos in que:\n",
    "\n",
    "                mod2 = (pos+k-1)%2 #先确定翻转后的奇偶性，这决定在哪个有序数据结构里二分查找\n",
    "                l = lst[mod2].bisect_left(max(-pos+k-1,pos-k+1))  # 出界和不出界分别对待，下同\n",
    "                r = lst[mod2].bisect_right(min(2*n-pos-k-1,pos+k-1))                \n",
    "                rmv.clear() # 由于SortedList要用下标进行遍历，因此先遍历后移除，rmv存储待移除元素\n",
    "                for j in range(l,r):\n",
    "                    pos1 = lst[mod2][j]\n",
    "                    if pos1 in lst[mod2]:\n",
    "                        que1.add(pos1)\n",
    "                        rmv.add(pos1)\n",
    "                        res[pos1]=step\n",
    "                for ke in rmv:\n",
    "                    lst[mod2].remove(ke)\n",
    "\n",
    "            que = que1\n",
    "            step+=1\n",
    "        \n",
    "        return res\n",
    "                \n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        bs = set(banned)\n",
    "        dp = [-1] * n\n",
    "        q = deque()\n",
    "        q.append(p)\n",
    "        dp[p] = 0\n",
    "        odd = SortedList()\n",
    "        even = SortedList()\n",
    "        for i in range(n):\n",
    "            if i == p:\n",
    "                continue\n",
    "            if i not in bs:\n",
    "                if i & 1:\n",
    "                    odd.add(i)\n",
    "                else:\n",
    "                    even.add(i)\n",
    "        odd.add(n)\n",
    "        even.add(n)\n",
    "        while q:\n",
    "            tmp = q.popleft()\n",
    "            # print(tmp)\n",
    "            l = max(tmp - k + 1, k - 1 - tmp)\n",
    "            r = min(tmp + k - 1, 2 * n - 1 - k - tmp)\n",
    "            # print(tmp, l, r)\n",
    "            # print(odd, even)\n",
    "            if l & 1:\n",
    "                bl = odd.bisect_left(l)\n",
    "                # br = odd.bisect_right(r)\n",
    "                # print(bl, l, br, r)\n",
    "                # rm_ls = list()\n",
    "                while odd[bl] <= r:\n",
    "                    dp[odd[bl]] = dp[tmp] + 1\n",
    "                    q.append(odd[bl])\n",
    "                    odd.remove(odd[bl])\n",
    "                # for i in range(bl, br): \n",
    "                #     if i < len(odd) and dp[odd[i]] != -1:\n",
    "                #         dp[odd[i]] = dp[tmp] + 1\n",
    "                #         q.append(odd[i])\n",
    "                #         rm_ls.append(odd[i])\n",
    "                # for i in rm_ls:\n",
    "                #     odd.remove(i)\n",
    "            else:\n",
    "                bl = even.bisect_left(l)\n",
    "                while even[bl] <= r:\n",
    "                    dp[even[bl]] = dp[tmp] + 1\n",
    "                    q.append(even[bl])\n",
    "                    even.remove(even[bl])\n",
    "                # br = even.bisect_right(r)\n",
    "                # print(bl, l, br, r)\n",
    "                # rm_ls = list()\n",
    "                # for i in range(bl, br):\n",
    "                #     if i < len(even) and dp[even[i]] != -1:\n",
    "                #         dp[even[i]] = dp[tmp] + 1\n",
    "                #         q.append(even[i])\n",
    "                #         rm_ls.append(even[i])\n",
    "                        # even.remove(even[i])\n",
    "                # rl = [even[i] for i in range(bl, br) if i < len(even) and even[i] not in bs]\n",
    "                # for i in rm_ls:\n",
    "                #     even.remove(i)\n",
    "            # print(dp)\n",
    "        # print(odd, even)\n",
    "        for i in odd[:-1]:\n",
    "            dp[i] = -1\n",
    "        for i in even[:-1]:\n",
    "            dp[i] = -1\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        bs = set(banned)\n",
    "        dp = [-1] * n\n",
    "        q = deque()\n",
    "        q.append(p)\n",
    "        dp[p] = 0\n",
    "        odd = SortedList()\n",
    "        even = SortedList()\n",
    "        for i in range(n):\n",
    "            if i == p:\n",
    "                continue\n",
    "            if i not in bs:\n",
    "                if i & 1:\n",
    "                    odd.add(i)\n",
    "                else:\n",
    "                    even.add(i)\n",
    "        odd.add(n)\n",
    "        even.add(n)\n",
    "        while q:\n",
    "            tmp = q.popleft()\n",
    "            l = max(tmp - k + 1, k - 1 - tmp)\n",
    "            r = min(tmp + k - 1, 2 * n - 1 - k - tmp)\n",
    "            if l & 1:\n",
    "                bl = odd.bisect_left(l)\n",
    "                while odd[bl] <= r:\n",
    "                    dp[odd[bl]] = dp[tmp] + 1\n",
    "                    q.append(odd[bl])\n",
    "                    odd.remove(odd[bl])\n",
    "            else:\n",
    "                bl = even.bisect_left(l)\n",
    "                while even[bl] <= r:\n",
    "                    dp[even[bl]] = dp[tmp] + 1\n",
    "                    q.append(even[bl])\n",
    "                    even.remove(even[bl])\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        banned = set(banned)\n",
    "\n",
    "        ret = [-1] * n\n",
    "\n",
    "        s1 = []\n",
    "        s2 = []\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in banned and i != p:\n",
    "                if i % 2 == 0:\n",
    "                    s1.append(i)\n",
    "                else:\n",
    "                    s2.append(i)\n",
    "\n",
    "        s1 = SortedList(s1)\n",
    "        s2 = SortedList(s2)\n",
    "\n",
    "        print(s1, s2)\n",
    "\n",
    "        q = deque([(0, p)])\n",
    "\n",
    "        while q:\n",
    "            d, x = q.popleft()\n",
    "\n",
    "            if ret[x] == -1:\n",
    "                ret[x] = d\n",
    "            else:\n",
    "                continue\n",
    "\n",
    "            mi = max(x - k + 1, k - x - 1)\n",
    "            ma = min(x + k - 1, 2 * n - k - x - 1)\n",
    "\n",
    "            if mi % 2 == 0:\n",
    "                s = s1\n",
    "            else:\n",
    "                s = s2\n",
    "\n",
    "            idx = s.bisect_left(mi)\n",
    "\n",
    "            while len(s) > idx and s[idx] <= ma:\n",
    "                y = s.pop(idx)\n",
    "                q.append((d + 1, y))\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        from sortedcontainers import SortedList \n",
    "        remains = [SortedList(), SortedList()] \n",
    "        banned = set(banned) \n",
    "        for i in range(n) : \n",
    "            if i == p : continue \n",
    "            if i not in banned : remains[i % 2].add(i) \n",
    "        remains[0].add(n) ; remains[1].add(n) \n",
    "        q = deque([(0, p)]) \n",
    "        ans = [-1] * n \n",
    "        ans[p] = 0 \n",
    "        while q : \n",
    "            step, i = q.popleft() \n",
    "            ll = max(i - k + 1, k - 1 - i) \n",
    "            rr = min(i + k - 1, 2 * n - k - 1 - i) \n",
    "            s = remains[ll % 2] \n",
    "            idx = s.bisect_left(ll) \n",
    "            while s[idx] <= rr : \n",
    "                ii = s[idx] \n",
    "                s.remove(ii) \n",
    "                ans[ii] = step + 1 \n",
    "                q.append((step + 1, ii)) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        banned = set(banned)\n",
    "        ans = [-1] * n\n",
    "        re = [SortedList(), SortedList()]\n",
    "        for i in range(n):\n",
    "            if i not in banned and i != p:\n",
    "                re[i % 2].add(i)\n",
    "            \n",
    "        q = deque([(p, 0)])\n",
    "        while q:\n",
    "            node, d = q.popleft()\n",
    "            ans[node] = d\n",
    "\n",
    "            # 子数组的左边界的可选区间\n",
    "            l, r = max(node - k + 1, 0), min(node, n - k)\n",
    "            # 反转后 node 可以落到的区间范围\n",
    "            '''\n",
    "            i -> i + k - 1\n",
    "            node - i == i + k - 1 - x\n",
    "            -> x = i + k - 1 - (node - i)\n",
    "            '''\n",
    "            left = l + k - 1 - (node - l)\n",
    "            right = r + k - 1 - (node - r)\n",
    "            \n",
    "            s = re[left % 2]\n",
    "            idx = s.bisect_left(left)\n",
    "            while idx < len(s) and s[idx] <= right:\n",
    "                q.append((s.pop(idx), d + 1))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        banned = set(banned)\n",
    "\n",
    "        ret = [-1] * n\n",
    "\n",
    "        s1 = []\n",
    "        s2 = []\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in banned and i != p:\n",
    "                if i % 2 == 0:\n",
    "                    s1.append(i)\n",
    "                else:\n",
    "                    s2.append(i)\n",
    "\n",
    "        s1 = SortedList(s1)\n",
    "        s2 = SortedList(s2)\n",
    "\n",
    "        q = deque([(0, p)])\n",
    "\n",
    "        while q:\n",
    "            d, x = q.popleft()\n",
    "\n",
    "            if ret[x] == -1:\n",
    "                ret[x] = d\n",
    "            else:\n",
    "                continue\n",
    "\n",
    "            mi = max(x - k + 1, k - x - 1)\n",
    "            ma = min(x + k - 1, 2 * n - k - x - 1)\n",
    "\n",
    "            if mi % 2 == 0:\n",
    "                s = s1\n",
    "            else:\n",
    "                s = s2\n",
    "\n",
    "            idx = s.bisect_left(mi)\n",
    "\n",
    "            while len(s) > idx and s[idx] <= ma:\n",
    "                y = s.pop(idx)\n",
    "                q.append((d + 1, y))\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = {i : i for i in range(n)}\n",
    "    \n",
    "    def find(self, node):\n",
    "        path = []\n",
    "        # print(self.parent)\n",
    "        while node != self.parent[node]:\n",
    "            path.append(node)\n",
    "            node = self.parent[node]\n",
    "        for p in path:\n",
    "            self.parent[p] = node \n",
    "        return node \n",
    "    \n",
    "    def union(self, n1, n2):\n",
    "        p1 = self.find(n1)\n",
    "        p2 = self.find(n2)\n",
    "        if p1 != p2:\n",
    "            self.parent[p1] = p2 \n",
    "\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        banned = set(banned) | {p}\n",
    "        unseen = [[], []]\n",
    "        for i in range(n):\n",
    "            if i not in banned:\n",
    "                unseen[i % 2].append(i)\n",
    "        unseen[0].append(n)\n",
    "        unseen[1].append(n)\n",
    "        uf = [UnionFind(len(unseen[0])), UnionFind(len(unseen[1]))]\n",
    "        res = [-1] * n \n",
    "        queue = collections.deque([[p, 0]])\n",
    "        while queue:\n",
    "            cur, step = queue.popleft()\n",
    "            res[cur] = step \n",
    "            left, right = max(cur - k + 1, k - 1 - cur), min(cur + k - 1, 2 * n - k - 1 - cur)\n",
    "            flag = left % 2 \n",
    "            idx = bisect_left(unseen[flag], left)\n",
    "            idx = uf[flag].find(idx)\n",
    "            while unseen[flag][idx] <= right:\n",
    "                queue.append([unseen[flag][idx], step + 1])\n",
    "                uf[flag].union(idx, idx + 1)\n",
    "                idx = uf[flag].find(idx)\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = {i : i for i in range(n)}\n",
    "    \n",
    "    def find(self, node):\n",
    "        path = []\n",
    "        while node != self.parent[node]:\n",
    "            path.append(node)\n",
    "            node = self.parent[node]\n",
    "        for p in path:\n",
    "            self.parent[p] = node \n",
    "        return node \n",
    "    \n",
    "    def union(self, n1, n2):\n",
    "        p1 = self.find(n1)\n",
    "        p2 = self.find(n2)\n",
    "        if p1 != p2:\n",
    "            self.parent[p1] = p2 \n",
    "\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        banned = set(banned) | {p}\n",
    "        even = [i for i in range(0, n, 2) if i not in banned]\n",
    "        odd = [i for i in range(1, n, 2) if i not in banned]\n",
    "        unseen = [even + [n], odd + [n]]\n",
    "        uf = [UnionFind(len(unseen[0])), UnionFind(len(unseen[1]))]\n",
    "        queue = collections.deque([[p, 0]])\n",
    "        res = [-1] * n \n",
    "        while queue:\n",
    "            i, step = queue.popleft()\n",
    "            res[i] = step \n",
    "            left = max(k - 1 - i, i - k + 1)\n",
    "            right = min(n - k + n - 1 - i, i + k - 1)\n",
    "            flag = left % 2\n",
    "            idx = bisect.bisect_left(unseen[flag], left)\n",
    "            idx = uf[flag].find(idx)\n",
    "            while unseen[flag][idx] <= right:\n",
    "                queue.append([unseen[flag][idx], step + 1])\n",
    "                uf[flag].union(idx, idx + 1)\n",
    "                idx = uf[flag].find(idx)\n",
    "        return res\n",
    "\n",
    "\n",
    "        while queue:\n",
    "            cur, step = queue.popleft()\n",
    "            res[cur] = step\n",
    "            left, right = max(cur - k + 1, k - 1 - cur), min(cur + k - 1, n - k + n - 1 - cur)\n",
    "            flag = left % 2 \n",
    "            idx = bisect.bisect_left(unseen[flag], left)\n",
    "            idx = dsu[flag].find(idx)\n",
    "            while unseen[flag][idx] <= right:\n",
    "                queue.append([unseen[flag][idx], step + 1])\n",
    "                dsu[flag].union(idx, idx + 1)\n",
    "                idx = dsu[flag].find(idx)\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = {i : i for i in range(n)}\n",
    "    \n",
    "    def find(self, node):\n",
    "        path = []\n",
    "        while node != self.parent[node]:\n",
    "            path.append(node)\n",
    "            node = self.parent[node]\n",
    "        for p in path:\n",
    "            self.parent[p] = node \n",
    "        return node \n",
    "    \n",
    "    def union(self, n1, n2):\n",
    "        p1 = self.find(n1)\n",
    "        p2 = self.find(n2)\n",
    "        if p1 != p2:\n",
    "            self.parent[p1] = p2 \n",
    "\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        banned = set(banned) | {p}\n",
    "        even = [i for i in range(0, n, 2) if i not in banned]\n",
    "        odd = [i for i in range(1, n, 2) if i not in banned]\n",
    "        unseen = [even + [n], odd + [n]]\n",
    "        uf = [UnionFind(len(unseen[0])), UnionFind(len(unseen[1]))]\n",
    "        queue = collections.deque([[p, 0]])\n",
    "        res = [-1] * n \n",
    "        while queue:\n",
    "            i, step = queue.popleft()\n",
    "            res[i] = step \n",
    "            left = max(k - 1 - i, i - k + 1)\n",
    "            right = min(n - k + n - 1 - i, i + k - 1)\n",
    "            flag = left % 2\n",
    "            idx = bisect.bisect_left(unseen[flag], left)\n",
    "            idx = uf[flag].find(idx)\n",
    "            while unseen[flag][idx] <= right:\n",
    "                queue.append([unseen[flag][idx], step + 1])\n",
    "                uf[flag].union(idx, idx + 1)\n",
    "                idx = uf[flag].find(idx)\n",
    "        return res\n",
    "\n",
    "\n",
    "        while queue:\n",
    "            cur, step = queue.popleft()\n",
    "            res[cur] = step\n",
    "            left, right = max(cur - k + 1, k - 1 - cur), min(cur + k - 1, n - k + n - 1 - cur)\n",
    "            flag = left % 2 \n",
    "            idx = bisect.bisect_left(unseen[flag], left)\n",
    "            idx = dsu[flag].find(idx)\n",
    "            while unseen[flag][idx] <= right:\n",
    "                queue.append([unseen[flag][idx], step + 1])\n",
    "                dsu[flag].union(idx, idx + 1)\n",
    "                idx = dsu[flag].find(idx)\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        ans = [-1] * n\n",
    "        ans[p] = 0\n",
    "        if k == 1: return ans\n",
    "        if k == n:\n",
    "            if n == 2*p + 1: return ans\n",
    "            q = n-1-p\n",
    "            if q not in banned: ans[q] = 1\n",
    "            return ans\n",
    "        pa = list(range(n+2))\n",
    "        we = [1] * (n+2)\n",
    "        def find(x):\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        for i in banned: pa[i] = i+2\n",
    "        pa[p] = p+2\n",
    "        q = [p]\n",
    "        while q:\n",
    "            new_q = []\n",
    "            for x in q:\n",
    "                min_val = max(x-k+1,k-1-x)\n",
    "                max_val = min(x+k-1,2*n-k-x-1)\n",
    "                y = find(min_val)\n",
    "                while y <= max_val:\n",
    "                    ans[y] = ans[x] + 1\n",
    "                    new_q.append(y)\n",
    "                    pa[y] = y+2\n",
    "                    y = find(y+2)\n",
    "            q = new_q\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n",
    "        s = set(banned) | {p}\n",
    "        not_banned = [[], []]\n",
    "        for i in range(n):\n",
    "            if i not in s:\n",
    "                not_banned[i % 2].append(i)\n",
    "        not_banned[0].append(n)\n",
    "        not_banned[1].append(n)  # 哨兵\n",
    "\n",
    "        fa = [list(range(len(not_banned[0]))), list(range(len(not_banned[1])))]\n",
    "\n",
    "        def find(i: int, x: int) -> int:\n",
    "            f = fa[i]\n",
    "            if f[x] != x:\n",
    "                f[x] = find(i, f[x])\n",
    "            return f[x]\n",
    "\n",
    "        def merge(i: int, from_: int, to: int) -> None:\n",
    "            x, y = find(i, from_), find(i, to)\n",
    "            fa[i][x] = y\n",
    "\n",
    "        ans = [-1] * n\n",
    "        q = [p]\n",
    "        step = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i in tmp:\n",
    "                ans[i] = step\n",
    "                # 从 mn 到 mx 的所有位置都可以翻转到\n",
    "                mn = max(i - k + 1, k - i - 1)\n",
    "                mx = min(i + k - 1, n * 2 - k - i - 1)\n",
    "                a = not_banned[mn % 2]\n",
    "                j = find(mn % 2, bisect_left(a, mn))\n",
    "                while a[j] <= mx:\n",
    "                    q.append(a[j])\n",
    "                    merge(mn % 2, j, j + 1)  # 删除 j\n",
    "                    j = find(mn % 2, j + 1)\n",
    "            step += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReverseOperations(self, n: int, p: int, banned, k: int) :\n",
    "        jumprange=[]\n",
    "        banned=set(banned)\n",
    "        for i in range(n):\n",
    "            jumprange.append([k-1-2*min(k-1,i),k-1-2*max(0,i+k-n)])\n",
    "        father=[[i for i in range(0,n+2,2)],[i for i in range(1,n+2,2)]]\n",
    "        def find(i,x):\n",
    "            if x==father[i][x//2]:\n",
    "                return x\n",
    "            else:\n",
    "                father[i][x//2]=find(i,father[i][x//2])\n",
    "                return father[i][x//2]\n",
    "        def union(i,a):#将i组元素a删除，使a的下一个为b\n",
    "            father[i][find(i,a)//2]=find(i,a+2)   \n",
    "        L=[-1]*n\n",
    "        L[p]=0\n",
    "        next={p}\n",
    "        count=0\n",
    "        while next!=set():\n",
    "            count+=1\n",
    "            now=next\n",
    "            next=set()\n",
    "            for i in now:\n",
    "                s=k-1-2*min(k-1,i)+i\n",
    "                M=k-1-2*max(0,i+k-n)+i\n",
    "                flag=s%2\n",
    "                while s<=M:\n",
    "                    if s not in banned and L[s]==-1:\n",
    "                        L[s]=count\n",
    "                        next.add(s)\n",
    "                        union(flag,s)\n",
    "                    elif s in banned:\n",
    "                        union(flag,s)\n",
    "                    s=find(flag,s+2)\n",
    "        return L"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
